1. Field of the Invention
Present invention relates to encoders and decoders for communication channels, and more particularly to convolutional interleavers and de-interleavers which are used in communication channels for the purposes of reducing the effect of burst-type errors in communication channels.
2. Description of Related Art
In data communication channels, one technique for managing errors is based on error correction and detection codes, such as the Reed-Solomon encoding and decoding techniques. According to these error correction and detection coding techniques, the data stream is transformed into a sequence of error protected packets of data. Errors which occur within the error protected packets, can be detected and in many cases corrected.
The error correcting and detecting codes in common use are very good at detecting and correcting isolated bit errors which occur in a communication channel. However, in a channel which is subject to burst-type errors, that is errors which will affect a large number of bits of data at a time, typical error correction and detection codes are insufficient. Burst-type errors often occur because of disturbances in the transmission path. Convolutional interleaving and de-interleaving techniques on either end of the transmission path are used to interleave the packet data so that the effects of burst errors become distributed when the packet data is de-interleaved, and do not overwhelm the error correcting and detecting codes.
For example, an emerging telecommunications standard for digital broadcasting systems for television, sound and data service is under development by the European Telecommunications Standards Institute (ETSI). This standard known as ETS300 412, published December 1994 specifies a system for performing the adaptation of base band television signals based on transport multiplex adaptation and randomization for energy dispersal; outer coding based on Reed- Solomon coding, convolutional interleaving, inner-coding based on punctured convolutional codes or Viterbi coding, base band shaping for modulation and actual modulation. The system includes a Reed-Solomon error correction and detection code, and convolutional interleaving to randomize error bursts on a byte basis in order to improve the burst error correction capability of the Reed-Solomon coder.
FIGS. 1 and 2 illustrate convolutional interleaving and de-interleaving respectively. In convolutional interleaving, as shown in FIG. 1, the interleaver comprises a number I+1 of rows, as shown as rows 0 through I in the FIG. 1. The rows after the first row consist of a first-in and first-out FIFO buffer having a number of cells which have a depth of M units of data. First row, Row 0 has 0 cells. The second row, Row 1 has one M unit cell and so on until the last row, Row I includes I M unit cells in the FIFO. An error protected packet enters the interleaver from the left in FIG. 1. The first byte of the error protected packet is supplied to Row 0. The second byte of the error protected packet is supplied to Row 1, and so on. On the output, the data is read from the outputs of the FIFOs in a counter-clockwise kind of rotation. Thus, the first byte is read from Row 0, the second byte is read from the output of the FIFO in Row 1, the second byte is read from the output of FIFO in Row 2, and so on until the last byte is read from the output of the FIFO in Row I for a given cycle through the interleaver output.
Considering a simple case in which I+1 is 3 (I=2), and M is 1, considering where the FIFOs are all initialized to zero, in a first clock cycle, the first byte is supplied on Row 0 directly through to the output. The second byte is stored in the FIFO in row 1, and 0 is supplied to the output at Row 1. The third byte is stored to the FIFO in Row 2, and 0 is supplied to the output at Row 2. The fourth byte is supplied directly from the input at Row 0 to the output. The fifth byte is stored in the FIFO in Row 1, and the second byte is read from the FIFO in Row I as output. The sixth byte is read to the FIFO at Row 2, and 0 is supplied at the output of Row 2. The seventh byte is supplied directly across Row 0. The eighth byte is supplied to the FIFO in Row 1, and the fourth byte is read from the FIFO in Row 1. The ninth byte is supplied to the FIFO in Row 2, and the third byte is read from the output of FIFO in Row 2, and so on. Therefore, for the input 1, 2, 3, 4, 5, 6, 7, 8, 9, . . . the output generated is 1 0 0 4 2 0 7 5 3 . . .
FIG. 2 illustrates the convolutional de-interleaver. The de-interleaver has a structure which is symmetrical with that of the interleaver. Thus, the first row of the de-interleaver has a FIFO with I cells which are M units deep. The last row, Row I, has no cells. The next to last row, I-1 has one cell in FIFO, and so on in the Figure. The de-interleaver receives the interleaved data on the left and writes it into the FIFOs in a clockwise right rotation as before. Thus, for the input 1 0 0 4 2 0 7 5 3 10 8 6 . . . which is generated by the interleaver, when I+1=3 and M=1, the first byte "1" is supplied into the FIFO at Row 0 and the output is zero, where in this embodiment Row 0 corresponds to the Row I-2 in FIG. 2. Second byte, "0", is supplied to the FIFO in Row I-1 and zero is output. The third byte "0" is supplied directly through Row I. The fourth byte "4" is supplied to the FIFO in Row I-2 and zero is output. The fifth byte "2" is supplied to the FIFO at Row I-1 and zero is output, and the sixth byte "0" is supplied directly through row I to the output. The seventh byte "7" is written to the FIFO in Row I-2, and the first byte "1" is supplied to as output. The eighth byte "5" is supplied to the FIFO in Row I-1, and the second byte "2" is supplied as output. The ninth byte "3" is supplied directly across from Row I, and so on.
The output pattern is 0 0 0 1 2 3 4 5 6 . . . .
Conceptually, the convolutional interleaver and de-interleaver of FIGS. 1 and 2 can be implemented by physical shift registers having the specified lengths. However, an exact hardware implementation of this architecture is very inefficient in terms of silicon area and gate count.
A more preferred method in the prior art is shown in FIG. 3. The system includes a memory 10, which is connected to receive addresses for read or write accesses to the memory across line 11. The address on line 11 is supplied by address select logic 12. The address select logic is connected to circuitry which provides address control for each of the separate virtual FIFOs set up in the memory 10. Thus, the first FIFO is implemented by a counter 13 for Row 0, which applies the address for Row 0 on line 14. A counter 15 for Row 1 is added by adder 16 to an offset 17 to generate an address for the FIFO in Row 1 on line 18. In similar fashion, a counter 19 for Row 2, and an offset for the FIFO of Row 2 on line 20 are supplied to adder 21 which supplies an address on line 22 for the FIFO of Row 2. A counter 23 and an offset 24 for the row where I=3, are supplied to an adder 25 to generate an address on line 26 for the row where I=3. Finally, for the row I, a counter 27 and an offset 28 are supplied to an adder 29 to generate the address on line 30 for the last FIFO row. Control logic 31 keeps track of the read and write process and controls the address select logic 12 with signals on line 32.
Thus, virtual FIFOs are implemented in single or dual port RAM. The read and write addresses with proper offsets are generated with separate adders for each row. While this technique is useful, and improves over the standard FIFO approach, the hardware implementation of the architecture becomes inefficient as the number of FIFOS, based on the I parameter, increases. Furthermore, the implementation is not configurable with various M and I variables, but rather these values determine the number of counters needed and the width of the adders. Finally, separate address generators are needed for the interleave and de-interleave directions.
Thus, it is desirable to provide an interleaver/de-interleaver architecture for use in the encoding and decoding of communication channels which has a scalable architecture for increasing complexity of the interleaver and de-interleaver algorithm, and utilizes less space on integrated circuits using the technique.